#include <iostream>
#include <algorithm>

template<typename Iter>
void insertion_sort(Iter beg, Iter end){
	for(Iter i=beg; i!=end; ++i){
		std::rotate(std::upper_bound(beg,i,*i),i,i+1);
		std::for_each(beg,end,print<typename>);
		std::cout<<std::endl;
	}
}

/**
int main(){
int array[] = {10,9,8,7,6,5,4,3,2,1};
insertion_sort(&array[0],&array[10]);
}
**/